package string

import (
	"container/list"
	"fmt"
)

// LengthOfLongestDistinctSubstring 最长不重复子串的长度
// leetcode3
// s = "abcabcbb"  3
// s = "bbbbb"     1
// s = "pwwkew"    3
// ""  0
func LengthOfLongestDistinctSubstring(s string) int {
	var (
		hash      = make(map[uint8]int)
		leftBound int
		maxLength int
	)

	for i := 0; i < len(s); i++ {
		// 这个关注的左边界 和 hash查找
		if pi, ok := hash[s[i]]; ok {
			// 边界问题不能等效 左边界不能回退
			if leftBound < pi+1 {
				leftBound = pi + 1
			}
		}

		// 无论 有没有都要进去
		hash[s[i]] = i
		// 应该每次都要重新计算最长子串
		cLength := i - leftBound + 1
		if cLength > maxLength {
			maxLength = cLength
		}
	}

	return maxLength
}

// LongestPalindrome 最长的回文子串
func LongestPalindrome(s string) string {
	if len(s) < 2 {
		return s
	}

	var (
		gLeft = 0
		gLen  = 0
		dp    = make([][]bool, len(s))
	)

	for i := 0; i < len(dp); i++ {
		dp[i] = make([]bool, len(s))
	}

	for sl := 1; sl <= len(s); sl++ {
		// left bound, right bound = left + L - 1
		for left := 0; left < len(s); left++ {
			// 处理边界
			right := left + sl - 1
			if right >= len(s) || left > right {
				break
			}

			// 按照 分段函数判断
			if right == left {
				dp[left][right] = true
			} else if right-left == 1 {
				if s[right] == s[left] {
					dp[left][right] = true
				} else {
					dp[left][right] = false
				}
			} else {
				if s[left] == s[right] && dp[left+1][right-1] {
					dp[left][right] = true
				} else {
					dp[left][right] = false
				}
			}

			if dp[left][right] {
				subLen := right - left + 1
				if subLen > gLen {
					gLen = subLen
					gLeft = left
				}
			}
		}
	}

	// golang 的切片 [a,b) 都是索引
	return s[gLeft : gLeft+gLen]
}

// ConvertZ 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
func ConvertZ(s string, numRows int) string {
	if numRows == 1 {
		return s
	}

	var (
		i  = 0
		j  = 0
		dp = make([][]uint8, numRows)
		f  = true // f: true 增  false 减
	)

	for i := 0; i < len(dp); i++ {
		dp[i] = make([]uint8, len(s))
	}

	for p := 0; p < len(s); p++ {

		if !f {
			j++
		}

		dp[i][j] = s[p]

		// 如果i 增; i∈[0, numRows) ==> i++; i == numRows - 1 ==> f = false, i --
		if f {
			if i < numRows-1 {
				i++
			} else {
				f = false
				if i > 0 {
					i--
				}
			}
		} else {
			if i > 0 {
				i--
			} else {
				f = true
				if i < numRows-1 {
					i++
				}
			}
		}
	}

	buf, pi := make([]uint8, len(s)), 0
	for _, arr := range dp {
		for _, char := range arr {
			//fmt.Printf("%s  ", string(char))
			if char != 0 {
				buf[pi] = char
				pi++
			}
		}

		//fmt.Println()
	}

	return string(buf)
}

// IsMatch 正则匹配
// leetcode10 todo: 10. 正则匹配 Level: High
// 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
//
// '.' 匹配任意单个字符
// '*' 匹配零个或多个前面的那一个元素
// 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串
func IsMatch(s string, p string) bool {
	return false
}

// LongestCommonPrefix 字符数组中的最长公共子串
// leetcode14 字符数组中的最长公共子串
func LongestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}

	if len(strs) == 1 {
		return strs[0]
	}

	mid := len(strs) >> 1
	leftPrefix := LongestCommonPrefix(strs[:mid])
	rightPrefix := LongestCommonPrefix(strs[mid:])

	i := 0
	for ; i < len(leftPrefix) && i < len(rightPrefix); i++ {
		if leftPrefix[i] != rightPrefix[i] {
			break
		}
	}

	return leftPrefix[:i]
}

// LetterCombinations 电话号码的字母组合 就是遍历排序组合啊
// leetcode17 电话号码的字母组合
func LetterCombinations(digits string) []string {
	if len(digits) == 0 {
		return make([]string, 0)
	}

	var (
		res  []string
		hash = map[uint8][]string{
			'2': {"a", "b", "c"},
			'3': {"d", "e", "f"},
			'4': {"g", "h", "i"},
			'5': {"j", "k", "l"},
			'6': {"m", "n", "o"},
			'7': {"p", "q", "r", "s"},
			'8': {"t", "u", "v"},
			'9': {"w", "x", "y", "z"},
		}
	)
	res = hash[digits[0]]
	for i := 1; i < len(digits); i++ {
		arr := hash[digits[i]]
		tmp, pi := make([]string, len(arr)*len(res)), 0
		for k := 0; k < len(res); k++ {
			for j := 0; j < len(arr); j++ {
				tmp[pi] = res[k] + arr[j]
				pi++
			}
		}
		res = tmp
	}
	return res
}

// IsValid 判断是否是有效括号
// leetcode20 判断是否是有效括号 easy
// {[()]} == true  [{]} == false  需要 队列
func IsValid(s string) bool {
	if len(s)|1 == len(s) {
		return false
	}

	var (
		// 栈
		stack = list.New()
		hash  = map[uint8]uint8{
			']': '[',
			'}': '{',
			')': '(',
		}
	)

	for i := 0; i < len(s); i++ {
		if c0, ok := hash[s[i]]; ok {
			if stack.Len() == 0 || stack.Remove(stack.Front()).(uint8) != c0 {
				return false
			}
		} else {
			stack.PushFront(s[i])
		}
	}

	return stack.Len() == 0
}

// StrStr 实现strStr() 函数 Brute-Force
// leetcode28: 实现strStr()  Level: easy
// 这不就是 字符串匹配到的索引值啊 字符串匹配的经典算法 这个搞可以 下面介绍KMP
func StrStr(haystack string, needle string) int {
	var (
		m = len(haystack)
		n = len(needle)
	)

	if n == 0 {
		return 0
	}

	for i := 0; i <= m-n; i++ {
		a, b := i, 0
		for b < len(needle) && haystack[a] == needle[b] {
			a++
			b++
		}

		if b == len(needle) {
			return i
		}
	}

	return -1
}

// StrStrKMP 实现strStr() 函数 使用KMP 算法
// leetcode28: 实现strStr()  Level: easy   时间复杂度 O(m+n)
// needle: 针;  haystack: 草垛;
// Author: Jinyun Liu
func StrStrKMP(haystack string, needle string) int {
	if needle == "" {
		return -1
	}

	next := Next(needle)
	fmt.Println(next)
	var (
		i int
		j int
	)

	for i < len(haystack) && j < len(next) {
		if j == 0 && haystack[i] != needle[j] {
			i++
		} else if haystack[i] != needle[j] {
			j = next[j-1]
		} else if haystack[i] == needle[j] {
			i++
			j++
		}

		if j == len(next) {
			return i - len(next)
		}
	}

	return -1
}

// KMP 算法 两点
// 每次匹配失败, 主串不变, 只需要调整模式串, 调整之后前缀已经匹配成功
// 模式串提供的信息 越多, 计算的次数 越少; 和模式串有关;
// 需要计算出 模式串的 next[];  Classical String-Matching Algorithm;

// 首先的写出来 next[j] = j 这个递推式
// 一些教材中 都是把模式串 从1 开始进行逻辑推理的;
// 1. next[j] = 0, j = 1
// 2. next[j] = max{k| 1<k<j & p1..pk = pj-k+1...pj}
// 3. next[j] = 1

// Next len=m
// S:			a a a b b a b
// PMT:			0 1 2 0 0 1 0      Partical matching table: 部分匹配表;
// 下面是变形, 只要在O(m)下完成 PMT 局部变量表的匹配; 当发现没有匹配的就可以查询这个表快速定位了;
// Next:		-10 1 2 0 0 1
// NextJ:		0 1 2 3 1 1 2
func Next(s string) []int {
	var (
		next = make([]int, len(s))
		j    = 0
		i    = 1
	)

	for i < len(s) {
		if s[j] == s[i] {
			next[i] = j + 1
			i++
			j++
		} else if j == 0 && s[j] != s[i] {
			next[i] = 0
			i++
		} else {
			j = next[j-1]
		}
	}

	return next
}

// 旋转词 123456
// 判断 两个字符串 是否互为旋转词  str1 str2
// 1. 首先长度 一定是相等
// 2. 可以以一个为主, 循环比较 O(N^2)
// 还可以两个 str + str; 可以把所有的旋转词 枚举 indexOf() 底层算法比 KMP 更优的常数;  KMP就无比经典;

// T1 T2 是否子树;  二叉树;  二叉树 的 先序遍历; 没有歧义的;

// 分析算法复杂度 需要对算法流程足够熟悉 sufficiently familiar;  pseudocode:
